<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 4.2.0">
<meta name="google-site-verification" content="SByO7HWUKwufO-witstBrFt-yyK6q3tUlCyYwkvYPiQ" />
<meta name="baidu-site-verification" content="orhaMjPwcS" />
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">

<link rel="stylesheet" href="//fonts.googleapis.com/css?family=Lato:300,300italic,400,400italic,700,700italic|Roboto Slab:300,300italic,400,400italic,700,700italic|Roboto Mono:300,300italic,400,400italic,700,700italic&display=swap&subset=latin,latin-ext">
<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  <link rel="stylesheet" href="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.css">

<script id="hexo-configurations">
    var NexT = window.NexT || {};
    var CONFIG = {"hostname":"lixiyan4633.gitee.io","root":"/","scheme":"Pisces","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"mac"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":true,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
  </script>

  <meta name="description" content="数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构算法Day04-链表">
<meta property="og:url" content="https://lixiyan4633.gitee.io/2020/03/19/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day04-%E9%93%BE%E8%A1%A8/index.html">
<meta property="og:site_name" content="喜延的个人博客">
<meta property="og:description" content="数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/d5/cd/d5d5bee4be28326ba3c28373808a62cd.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/b9/eb/b93e7ade9bb927baad1348d9a806ddeb.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/86/55/86cb7dc331ea958b0a108b911f38d155.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/cb/0b/cbc8ab20276e2f9312030c313a9ef70b.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/45/17/452e943788bdeea462d364389bd08a17.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/4f/68/4f63e92598ec2551069a0eef69db7168.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/05/6e/05a4a3b57502968930d517c934347c6e.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/7d/c7/7d22d9428bdbba96bfe388fe1e3368c7.jpg">
<meta property="og:image" content="https://static001.geekbang.org/resource/image/4a/f8/4a701dd79b59427be654261805b349f8.jpg">
<meta property="article:published_time" content="2020-03-19T02:47:11.000Z">
<meta property="article:modified_time" content="2020-03-19T12:30:29.722Z">
<meta property="article:author" content="李喜延">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="链表">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://static001.geekbang.org/resource/image/d5/cd/d5d5bee4be28326ba3c28373808a62cd.jpg">

<link rel="canonical" href="https://lixiyan4633.gitee.io/2020/03/19/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day04-%E9%93%BE%E8%A1%A8/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome : false,
    isPost : true
  };
</script>

  <title>数据结构算法Day04-链表 | 喜延的个人博客</title>
  






  <noscript>
  <style>
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-header { opacity: initial; }

  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage">
  <div class="container use-motion">
    <div class="headband"></div>

    <header class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏">
      <span class="toggle-line toggle-line-first"></span>
      <span class="toggle-line toggle-line-middle"></span>
      <span class="toggle-line toggle-line-last"></span>
    </div>
  </div>

  <div class="site-meta">

    <div>
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">喜延的个人博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">我的大数据的之路</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger">
    </div>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
        <li class="menu-item menu-item-home">

    <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>首页</a>

  </li>
        <li class="menu-item menu-item-tags">

    <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>标签</a>

  </li>
        <li class="menu-item menu-item-categories">

    <a href="/categories/" rel="section"><i class="fa fa-fw fa-th"></i>分类</a>

  </li>
        <li class="menu-item menu-item-archives">

    <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>归档</a>

  </li>
        <li class="menu-item menu-item-about">

    <a href="/about/" rel="section"><i class="fa fa-fw fa-user"></i>关于</a>

  </li>
  </ul>

</nav>
</div>
    </header>

    
  <div class="back-to-top">
    <i class="fa fa-arrow-up"></i>
    <span>0%</span>
  </div>


    <main class="main">
      <div class="main-inner">
        <div class="content-wrap">
          

          <div class="content">
            

  <div class="posts-expand">
      
  
  
  <article itemscope itemtype="http://schema.org/Article" class="post-block " lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="https://lixiyan4633.gitee.io/2020/03/19/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day04-%E9%93%BE%E8%A1%A8/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="https://tva1.sinaimg.cn/large/00831rSTly1gcyel996b4j30oa0oc1kx.jpg">
      <meta itemprop="name" content="李喜延">
      <meta itemprop="description" content="愿世界和平">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="喜延的个人博客">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          数据结构算法Day04-链表
        </h1>

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>
              

              <time title="创建时间：2020-03-19 10:47:11 / 修改时间：20:30:29" itemprop="dateCreated datePublished" datetime="2020-03-19T10:47:11+08:00">2020-03-19</time>
            </span>
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
                  <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" itemprop="url" rel="index"><span itemprop="name">数据结构</span></a>
                </span>
            </span>

          
            <div class="post-description">数据结构算法打卡，参考的王铮老师在极客时间上的《数据结构与算法之美》<br> <img src="https://static001.geekbang.org/resource/image/aa/25/aa5000d3a2079c75a5cbe32772d52625.jpg"></div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="1-概念："><a href="#1-概念：" class="headerlink" title="1.概念："></a>1.概念：</h1><p>链表：链表（Linked list）是一种线性结构：有且只有一个根节点，且每个节点最多有一个直接前驱和一个直接后继的非空数据结构。</p>
<p>链表与数组的区别：从底层结构看，数组由一段连续的内存构成，链表则恰好相反，它通过指针将零散的内存块串联起来</p>
<p><img src="https://static001.geekbang.org/resource/image/d5/cd/d5d5bee4be28326ba3c28373808a62cd.jpg" alt="img"></p>
<h1 id="2-分类"><a href="#2-分类" class="headerlink" title="2.分类"></a>2.分类</h1><p>链表主要分为单向链表、循环(环形)链表和双向链表三类，其中根据上面的解释我们把内存块在链表中叫做结点。</p>
<h2 id="2-1-单链表："><a href="#2-1-单链表：" class="headerlink" title="2.1 单链表："></a>2.1 单链表：</h2><p>由<strong>数据结点</strong> data 和<strong>后继指针</strong> next组成，data存储数据，next存储下个结点的地址。</p>
<p><img src="https://static001.geekbang.org/resource/image/b9/eb/b93e7ade9bb927baad1348d9a806ddeb.jpg" alt="img"></p>
<h2 id="2-2-循环-环形-链表："><a href="#2-2-循环-环形-链表：" class="headerlink" title="2.2 循环(环形)链表："></a>2.2 循环(环形)链表：</h2><p>循环链表是一种特殊的单链表，位移的区别在于尾巴结点，单链表 <code>尾结点 后继指针 -&gt; null</code>代表链表结束，在循环链表中 <code>尾结点 后继指针-&gt;头结点地址</code>，它像一个环一样首尾相连，所以叫作“循环”链表。</p>
<p><img src="https://static001.geekbang.org/resource/image/86/55/86cb7dc331ea958b0a108b911f38d155.jpg" alt="img"></p>
<h2 id="2-3-双向链表："><a href="#2-3-双向链表：" class="headerlink" title="2.3 双向链表："></a>2.3 双向链表：</h2><p>单链表只有一个后继指针next,但是双向链表拥有多一个<strong>前驱指针</strong>prev,可以看到这样会浪费空间，但是可以支持双向遍历。</p>
<p><img src="https://static001.geekbang.org/resource/image/cb/0b/cbc8ab20276e2f9312030c313a9ef70b.jpg" alt="img"></p>
<h1 id="3-操作"><a href="#3-操作" class="headerlink" title="3.操作"></a>3.操作</h1><h2 id="3-1-单链表插入和删除"><a href="#3-1-单链表插入和删除" class="headerlink" title="3.1 单链表插入和删除"></a>3.1 单链表插入和删除</h2><p>如图所示，由于链表是一段不连续的空间组成，所以在插入删除都很高效，只需要控制 <strong>后继指针</strong>的指向即可。</p>
<p>时间复杂度: O(1)</p>
<p><img src="https://static001.geekbang.org/resource/image/45/17/452e943788bdeea462d364389bd08a17.jpg" alt="img"></p>
<h2 id="3-2-单链表查找"><a href="#3-2-单链表查找" class="headerlink" title="3.2 单链表查找"></a>3.2 单链表查找</h2><p>有利就会有弊，单链表插入和删除都很高效，得益于不连续的存储空间，但是如果要进行查找，因为不连续，所以无法直接根据数组寻址公式来定位结点地址，所以只能通过从头查询的方式，进行查询。</p>
<p>时间复杂度：O(n)</p>
<h2 id="3-3-双向链表插入和删除"><a href="#3-3-双向链表插入和删除" class="headerlink" title="3.3 双向链表插入和删除"></a>3.3 双向链表插入和删除</h2><p>链表插入删除误区：和数组读取一样，如果是根据 ”下标“，即指定地址或偏移，插入和删除的时间复杂度是O(1)，但是如果是删除某个值，就需要从头读取链表，时间复杂度为O(n)。</p>
<ul>
<li>给定值：需要遍历值，时间复杂度为O(n)</li>
<li>给定指向结点</li>
</ul>
<p>如我要删除 P10结点：</p>
<ol>
<li>从头找到 P10的上个结点 P9；</li>
<li>将P9.next -&gt; p10.next</li>
</ol>
<p>其中P9,P10,P11代表地址</p>
<p>在第1步，我们如果使用单向链表需要 从头结点找到P9，时间复杂度为O(n)，当使用双向链表，由于有<strong>前驱指针</strong>prev,我们能很好的获取他的前结点，时间复杂度为O(1)。</p>
<h2 id="3-3-双向链表查找"><a href="#3-3-双向链表查找" class="headerlink" title="3.3 双向链表查找"></a>3.3 双向链表查找</h2><p>可以采用前后跑的思想，相比单链表只能单向查找，节省一半的时间。</p>
<blockquote>
<p>LinkedHashMap 底层采用双向链表</p>
</blockquote>
<h1 id="4-链表-VS-数组"><a href="#4-链表-VS-数组" class="headerlink" title="4.链表 VS 数组"></a>4.链表 VS 数组</h1><p><img src="https://static001.geekbang.org/resource/image/4f/68/4f63e92598ec2551069a0eef69db7168.jpg" alt="img"></p>
<ul>
<li>数组简单易用，效率高，因为是连续空间，可以预读取</li>
<li>链表没有大小限制，数组需要指定大小，超过了需要扩容搬移</li>
<li>链表高频次的删除和插入，会导致内存碎片，因为需要标记信息，所以占用空间大，可能导致频繁GC</li>
</ul>
<h1 id="5-LRU算法思路"><a href="#5-LRU算法思路" class="headerlink" title="5.LRU算法思路"></a>5.LRU算法思路</h1><p>维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"># 存储顺序 新 -&gt; 旧</span><br><span class="line">a -&gt; b -&gt; c -&gt; d</span><br></pre></td></tr></table></figure>

<p>1.如果访问c,  则删除c，把c放到头结点，重排的顺序为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">c -&gt; a -&gt; b -&gt; d</span><br></pre></td></tr></table></figure>

<p>2.如果是新数据e,分两种情况：</p>
<p>a. 缓存没满</p>
<p>直接插入头结点即可，重排顺序为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">e -&gt; a -&gt; b -&gt; c -&gt; d</span><br></pre></td></tr></table></figure>

<p>b. 缓存满了</p>
<p>就需要删除末尾数据，将新节点插入头结点，重排顺序为：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">e -&gt; a -&gt; b -&gt; c</span><br></pre></td></tr></table></figure>

<h1 id="6-链表的写法"><a href="#6-链表的写法" class="headerlink" title="6.链表的写法"></a>6.链表的写法</h1><h2 id="技巧一：理解指针或引用的含义"><a href="#技巧一：理解指针或引用的含义" class="headerlink" title="技巧一：理解指针或引用的含义"></a>技巧一：理解指针或引用的含义</h2><p>将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">p-&gt;next &#x3D; q</span><br></pre></td></tr></table></figure>

<p>相当于p结点的next指针存储q结点的内存地址。</p>
<h2 id="技巧二：警惕指针丢失和内存泄漏"><a href="#技巧二：警惕指针丢失和内存泄漏" class="headerlink" title="技巧二：警惕指针丢失和内存泄漏"></a>技巧二：警惕指针丢失和内存泄漏</h2><ul>
<li>插入结点时，一定要注意操作的顺序</li>
<li>删除链表结点时，也一定要记得手动释放内存空间</li>
</ul>
<p>在日常的操作，需要注意指针的指向，否则容易内存泄露，举个例子：</p>
<p><img src="https://static001.geekbang.org/resource/image/05/6e/05a4a3b57502968930d517c934347c6e.jpg" alt="img"></p>
<p>如图所示，我们希望在结点 a 和相邻的结点 b 之间插入结点 x，假设当前指针 p 指向结点 a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">p-&gt;next = x;  <span class="comment">// 将p的next指针指向x结点；</span></span><br><span class="line">x-&gt;next = p-&gt;next;  <span class="comment">// 将x的结点的next指针指向b结点；</span></span><br></pre></td></tr></table></figure>

<p>因为p-&gt;next在第二行已经变为了x的地址，所以 第二行就变成了</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">x-&gt;next = x</span><br></pre></td></tr></table></figure>

<p>造成内存泄露，实现上面效果，只需要反过来</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">x-&gt;next = p-&gt;next;  <span class="comment">// 将x的结点的next指针指向b结点；</span></span><br><span class="line">p-&gt;next = x;  <span class="comment">// 将p的next指针指向x结点；</span></span><br></pre></td></tr></table></figure>



<h2 id="技巧三：利用哨兵简化实现难度"><a href="#技巧三：利用哨兵简化实现难度" class="headerlink" title="技巧三：利用哨兵简化实现难度"></a>技巧三：利用哨兵简化实现难度</h2><p>主要针对链表的插入、删除操作，需要对插入<strong>第一个结点</strong>和<strong>删除最后一个结点</strong>的情况进行特殊处理，举个例子：</p>
<ul>
<li>单链表的插入：</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">new_node-&gt;next = p-&gt;next;</span><br><span class="line">p-&gt;next = new_node;</span><br></pre></td></tr></table></figure>

<p>针对空链表中插入第一个结点：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (head == <span class="keyword">null</span>) &#123;</span><br><span class="line">  head = new_node;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<ul>
<li>单链表删除：</li>
</ul>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">p-&gt;next = p-&gt;next-&gt;next;</span><br></pre></td></tr></table></figure>

<p>针对删除链表中的最后一个结点：</p>
<figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span> (head-&gt;next == <span class="keyword">null</span>) &#123;</span><br><span class="line">   head = <span class="keyword">null</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>由于都是在head指针出现问题，所以加一个结点作为带头结点，就可以避免这些问题：</p>
<p><img src="https://static001.geekbang.org/resource/image/7d/c7/7d22d9428bdbba96bfe388fe1e3368c7.jpg" alt="img"></p>
<p>下面是代码演示：</p>
<p>代码一：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="comment">// 在数组a中，查找key，返回key所在的位置</span></span><br><span class="line"><span class="comment">// 其中，n表示数组a的长度</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">char</span>* a, <span class="keyword">int</span> n, <span class="keyword">char</span> key)</span> </span>&#123;</span><br><span class="line">  <span class="comment">// 边界条件处理，如果a为空，或者n&lt;=0，说明数组中没有数据，就不用while循环比较了</span></span><br><span class="line">  <span class="keyword">if</span>(a == null || n &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line">  <span class="comment">// 这里有两个比较操作：i&lt;n和a[i]==key.</span></span><br><span class="line">  <span class="keyword">while</span> (i &lt; n) &#123;</span><br><span class="line">    <span class="keyword">if</span> (a[i] == key) &#123;</span><br><span class="line">      <span class="keyword">return</span> i;</span><br><span class="line">    &#125;</span><br><span class="line">    ++i;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>代码二：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="comment">// 在数组a中，查找key，返回key所在的位置</span></span><br><span class="line"><span class="comment">// 其中，n表示数组a的长度</span></span><br><span class="line"><span class="comment">// 我举2个例子，你可以拿例子走一下代码</span></span><br><span class="line"><span class="comment">// a = &#123;4, 2, 3, 5, 9, 6&#125;  n=6 key = 7</span></span><br><span class="line"><span class="comment">// a = &#123;4, 2, 3, 5, 9, 6&#125;  n=6 key = 6</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">find</span><span class="params">(<span class="keyword">char</span>* a, <span class="keyword">int</span> n, <span class="keyword">char</span> key)</span> </span>&#123;</span><br><span class="line">  <span class="keyword">if</span>(a == null || n &lt;= <span class="number">0</span>) &#123;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="comment">// 这里因为要将a[n-1]的值替换成key，所以要特殊处理这个值</span></span><br><span class="line">  <span class="keyword">if</span> (a[n<span class="number">-1</span>] == key) &#123;</span><br><span class="line">    <span class="keyword">return</span> n<span class="number">-1</span>;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="comment">// 把a[n-1]的值临时保存在变量tmp中，以便之后恢复。tmp=6。</span></span><br><span class="line">  <span class="comment">// 之所以这样做的目的是：希望find()代码不要改变a数组中的内容</span></span><br><span class="line">  <span class="keyword">char</span> tmp = a[n<span class="number">-1</span>];</span><br><span class="line">  <span class="comment">// 把key的值放到a[n-1]中，此时a = &#123;4, 2, 3, 5, 9, 7&#125;</span></span><br><span class="line">  a[n<span class="number">-1</span>] = key;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">int</span> i = <span class="number">0</span>;</span><br><span class="line">  <span class="comment">// while 循环比起代码一，少了i&lt;n这个比较操作</span></span><br><span class="line">  <span class="keyword">while</span> (a[i] != key) &#123;</span><br><span class="line">    ++i;</span><br><span class="line">  &#125;</span><br><span class="line">  </span><br><span class="line">  <span class="comment">// 恢复a[n-1]原来的值,此时a= &#123;4, 2, 3, 5, 9, 6&#125;</span></span><br><span class="line">  a[n<span class="number">-1</span>] = tmp;</span><br><span class="line">  </span><br><span class="line">  <span class="keyword">if</span> (i == n<span class="number">-1</span>) &#123;</span><br><span class="line">    <span class="comment">// 如果i == n-1说明，在0...n-2之间都没有key，所以返回-1</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">  &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">    <span class="comment">// 否则，返回i，就是等于key值的元素的下标</span></span><br><span class="line">    <span class="keyword">return</span> i;</span><br><span class="line">  &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>对比两段代码，在字符串 a 很长的时候，比如几万、几十万，你觉得哪段代码运行得更快点呢？答案是代码二，因为两段代码中执行次数最多就是 while 循环那一部分。第二段代码中，我们通过一个哨兵 a[n-1] = key，成功省掉了一个比较语句 i&lt;n，不要小看这一条语句，当累积执行万次、几十万次时，累积的时间就很明显了。</p>
<h2 id="技巧四：重点留意边界条件处理"><a href="#技巧四：重点留意边界条件处理" class="headerlink" title="技巧四：重点留意边界条件处理"></a>技巧四：重点留意边界条件处理</h2><p>用来检查链表代码是否正确的边界条件有这样几个：</p>
<ul>
<li>如果链表为空时，代码是否能正常工作？</li>
<li>如果链表只包含一个结点时，代码是否能正常工作？</li>
<li>如果链表只包含两个结点时，代码是否能正常工作？</li>
<li>代码逻辑在处理头结点和尾结点的时候，是否能正常工作？</li>
</ul>
<h2 id="技巧五：举例画图，辅助思考"><a href="#技巧五：举例画图，辅助思考" class="headerlink" title="技巧五：举例画图，辅助思考"></a>技巧五：举例画图，辅助思考</h2><p>可以通过画图的方式，降低错误</p>
<p><img src="https://static001.geekbang.org/resource/image/4a/f8/4a701dd79b59427be654261805b349f8.jpg" alt="img"></p>
<h2 id="技巧六：多写多练，没有捷径"><a href="#技巧六：多写多练，没有捷径" class="headerlink" title="技巧六：多写多练，没有捷径"></a>技巧六：多写多练，没有捷径</h2><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">package</span> com.lixiyan.algo.linklist;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> com.lixiyan.t1.ListNode;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span></span><br><span class="line"><span class="comment"> * 链表的一些基础算法</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * 1) 单链表反转</span></span><br><span class="line"><span class="comment"> * 2) 链表中环的检测</span></span><br><span class="line"><span class="comment"> * 3) 两个有序的链表合并</span></span><br><span class="line"><span class="comment"> * 4) 删除链表倒数第n个结点</span></span><br><span class="line"><span class="comment"> * 5) 求链表的中间结点</span></span><br><span class="line"><span class="comment"> *</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@author</span> lixiyan</span></span><br><span class="line"><span class="comment"> * <span class="doctag">@date</span> 2020/3/19 3:26 PM</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LinkedListAlgo</span> </span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line">        Node node = createNode(<span class="number">1</span>);</span><br><span class="line">        node.next = createNode(<span class="number">2</span>);</span><br><span class="line">        node.next.next = createNode(<span class="number">3</span>);</span><br><span class="line"></span><br><span class="line">        Node node2 = createNode(<span class="number">3</span>);</span><br><span class="line">        node2.next = createNode(<span class="number">4</span>);</span><br><span class="line">        node2.next.next = createNode(<span class="number">5</span>);</span><br><span class="line">        <span class="comment">// 单链表反转</span></span><br><span class="line">        reverse(node);</span><br><span class="line">        <span class="comment">// 链表中环的检测</span></span><br><span class="line">        checkCircle(node);</span><br><span class="line">        <span class="comment">// 两个有序的链表合并</span></span><br><span class="line">        mergeTwoLists(node,node2);</span><br><span class="line">        <span class="comment">// 删除链表倒数第n个结点</span></span><br><span class="line">        deleteLastKth(node,<span class="number">2</span>);</span><br><span class="line">        <span class="comment">// 求链表的中间结点</span></span><br><span class="line">        findMiddleNode(node);</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 单链表反转</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">reverse</span><span class="params">(Node list)</span> </span>&#123;</span><br><span class="line">        Node cur = list;</span><br><span class="line">        Node prev = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">while</span> (cur != <span class="keyword">null</span>)&#123;</span><br><span class="line">            Node next = cur.next;</span><br><span class="line">            <span class="comment">// 1-2-3  pre =1 cur =2  =&gt; 2-1</span></span><br><span class="line">            cur.next = prev;</span><br><span class="line">            <span class="comment">//</span></span><br><span class="line">            prev = cur;</span><br><span class="line">            cur = next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> prev;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 检测环</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">boolean</span> <span class="title">checkCircle</span><span class="params">(Node list)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (list == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line"></span><br><span class="line">        Node fast = list.next;</span><br><span class="line">        Node slow = list;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (fast != <span class="keyword">null</span> &amp;&amp; fast.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">            fast = fast.next.next;</span><br><span class="line">            slow = slow.next;</span><br><span class="line"></span><br><span class="line">            <span class="keyword">if</span> (slow == fast) <span class="keyword">return</span> <span class="keyword">true</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">false</span>;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 有序链表合并 Leetcode 21</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">mergeTwoLists</span><span class="params">(Node l1, Node l2)</span> </span>&#123;</span><br><span class="line">        <span class="comment">//利用哨兵结点简化实现难度 技巧三</span></span><br><span class="line">        Node soldier = createNode(<span class="number">0</span>);</span><br><span class="line">        Node p = soldier;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> ( l1 != <span class="keyword">null</span> &amp;&amp; l2 != <span class="keyword">null</span> )&#123;</span><br><span class="line">            <span class="keyword">if</span> ( l1.data &lt; l2.data )&#123;</span><br><span class="line">                p.next = l1;</span><br><span class="line">                l1 = l1.next;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span>&#123;</span><br><span class="line">                p.next = l2;</span><br><span class="line">                l2 = l2.next;</span><br><span class="line">            &#125;</span><br><span class="line">            p = p.next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (l1 != <span class="keyword">null</span>) &#123; p.next = l1; &#125;</span><br><span class="line">        <span class="keyword">if</span> (l2 != <span class="keyword">null</span>) &#123; p.next = l2; &#125;</span><br><span class="line">        <span class="keyword">return</span> soldier.next;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">// 删除倒数第K个结点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">deleteLastKth</span><span class="params">(Node list, <span class="keyword">int</span> k)</span> </span>&#123;</span><br><span class="line">        Node fast = list;</span><br><span class="line">        <span class="keyword">int</span> i = <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">while</span> (fast != <span class="keyword">null</span> &amp;&amp; i &lt; k) &#123;</span><br><span class="line">            fast = fast.next;</span><br><span class="line">            ++i;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (fast == <span class="keyword">null</span>) <span class="keyword">return</span> list;</span><br><span class="line"></span><br><span class="line">        Node slow = list;</span><br><span class="line">        Node prev = <span class="keyword">null</span>;</span><br><span class="line">        <span class="keyword">while</span> (fast.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">            fast = fast.next;</span><br><span class="line">            prev = slow;</span><br><span class="line">            slow = slow.next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span> (prev == <span class="keyword">null</span>) &#123;</span><br><span class="line">            list = list.next;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            prev.next = prev.next.next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> list;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// 求中间结点</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">findMiddleNode</span><span class="params">(Node list)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (list == <span class="keyword">null</span>) <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        Node fast = list;</span><br><span class="line">        Node slow = list;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">while</span> (fast != <span class="keyword">null</span> &amp;&amp; fast.next != <span class="keyword">null</span>) &#123;</span><br><span class="line">            fast = fast.next.next;</span><br><span class="line">            slow = slow.next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> slow;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">printAll</span><span class="params">(Node list)</span> </span>&#123;</span><br><span class="line">        Node p = list;</span><br><span class="line">        <span class="keyword">while</span> (p != <span class="keyword">null</span>) &#123;</span><br><span class="line">            System.out.print(p.data + <span class="string">" --&gt; "</span>);</span><br><span class="line">            p = p.next;</span><br><span class="line">        &#125;</span><br><span class="line">        System.out.println();</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> Node <span class="title">createNode</span><span class="params">(<span class="keyword">int</span> value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">new</span> Node(value, <span class="keyword">null</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">public</span> <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span> </span>&#123;</span><br><span class="line">        <span class="keyword">private</span> <span class="keyword">int</span> data;</span><br><span class="line">        <span class="keyword">private</span> Node next;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="title">Node</span><span class="params">(<span class="keyword">int</span> data, Node next)</span> </span>&#123;</span><br><span class="line">            <span class="keyword">this</span>.data = data;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="function"><span class="keyword">public</span> <span class="keyword">int</span> <span class="title">getData</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> data;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
    </div>

    
    
    

      <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/" rel="tag"><i class="fa fa-tag"></i> 数据结构</a>
              <a href="/tags/%E7%AE%97%E6%B3%95/" rel="tag"><i class="fa fa-tag"></i> 算法</a>
              <a href="/tags/%E9%93%BE%E8%A1%A8/" rel="tag"><i class="fa fa-tag"></i> 链表</a>
          </div>

        


        
    <div class="post-nav">
      <div class="post-nav-item">
    <a href="/2020/03/18/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E7%AE%97%E6%B3%95Day03-%E6%95%B0%E7%BB%84/" rel="prev" title="数据结构算法Day03-数组">
      <i class="fa fa-chevron-left"></i> 数据结构算法Day03-数组
    </a></div>
      <div class="post-nav-item">
    <a href="/2020/03/19/calcite%E6%95%99%E7%A8%8B04-%E8%87%AA%E5%AE%9A%E4%B9%89CSV%E6%95%B0%E6%8D%AE%E6%BA%90%E8%A1%A8%E6%9F%A5%E8%AF%A2/" rel="next" title="calcite教程04-自定义CSV数据源表查询">
      calcite教程04-自定义CSV数据源表查询 <i class="fa fa-chevron-right"></i>
    </a></div>
    </div>
      </footer>
    
  </article>
  
  
  
<div>
    
    <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------　　　　本文结束　<i class="fa fa-heart"></i>　感谢您的阅读　　　　-------------</div>
    
</div>


    
 </div>

  </div>


          </div>
          

<script>
  window.addEventListener('tabs:register', () => {
    let { activeClass } = CONFIG.comments;
    if (CONFIG.comments.storage) {
      activeClass = localStorage.getItem('comments_active') || activeClass;
    }
    if (activeClass) {
      let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
      if (activeTab) {
        activeTab.click();
      }
    }
  });
  if (CONFIG.comments.storage) {
    window.addEventListener('tabs:click', event => {
      if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
      let commentClass = event.target.classList[1];
      localStorage.setItem('comments_active', commentClass);
    });
  }
</script>

        </div>
          
  
  <div class="toggle sidebar-toggle">
    <span class="toggle-line toggle-line-first"></span>
    <span class="toggle-line toggle-line-middle"></span>
    <span class="toggle-line toggle-line-last"></span>
  </div>

  <aside class="sidebar">
    <div class="sidebar-inner">

      <ul class="sidebar-nav motion-element">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <!--noindex-->
      <div class="post-toc-wrap sidebar-panel">
          <div class="post-toc motion-element"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#1-概念："><span class="nav-number">1.</span> <span class="nav-text">1.概念：</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#2-分类"><span class="nav-number">2.</span> <span class="nav-text">2.分类</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#2-1-单链表："><span class="nav-number">2.1.</span> <span class="nav-text">2.1 单链表：</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-2-循环-环形-链表："><span class="nav-number">2.2.</span> <span class="nav-text">2.2 循环(环形)链表：</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#2-3-双向链表："><span class="nav-number">2.3.</span> <span class="nav-text">2.3 双向链表：</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#3-操作"><span class="nav-number">3.</span> <span class="nav-text">3.操作</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#3-1-单链表插入和删除"><span class="nav-number">3.1.</span> <span class="nav-text">3.1 单链表插入和删除</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-2-单链表查找"><span class="nav-number">3.2.</span> <span class="nav-text">3.2 单链表查找</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-3-双向链表插入和删除"><span class="nav-number">3.3.</span> <span class="nav-text">3.3 双向链表插入和删除</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#3-3-双向链表查找"><span class="nav-number">3.4.</span> <span class="nav-text">3.3 双向链表查找</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#4-链表-VS-数组"><span class="nav-number">4.</span> <span class="nav-text">4.链表 VS 数组</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#5-LRU算法思路"><span class="nav-number">5.</span> <span class="nav-text">5.LRU算法思路</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#6-链表的写法"><span class="nav-number">6.</span> <span class="nav-text">6.链表的写法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧一：理解指针或引用的含义"><span class="nav-number">6.1.</span> <span class="nav-text">技巧一：理解指针或引用的含义</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧二：警惕指针丢失和内存泄漏"><span class="nav-number">6.2.</span> <span class="nav-text">技巧二：警惕指针丢失和内存泄漏</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧三：利用哨兵简化实现难度"><span class="nav-number">6.3.</span> <span class="nav-text">技巧三：利用哨兵简化实现难度</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧四：重点留意边界条件处理"><span class="nav-number">6.4.</span> <span class="nav-text">技巧四：重点留意边界条件处理</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧五：举例画图，辅助思考"><span class="nav-number">6.5.</span> <span class="nav-text">技巧五：举例画图，辅助思考</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#技巧六：多写多练，没有捷径"><span class="nav-number">6.6.</span> <span class="nav-text">技巧六：多写多练，没有捷径</span></a></li></ol></li></ol></div>
      </div>
      <!--/noindex-->

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image" alt="李喜延"
      src="https://tva1.sinaimg.cn/large/00831rSTly1gcyel996b4j30oa0oc1kx.jpg">
  <p class="site-author-name" itemprop="name">李喜延</p>
  <div class="site-description" itemprop="description">愿世界和平</div>
</div>
<div class="site-state-wrap motion-element">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
          <a href="/archives/">
        
          <span class="site-state-item-count">25</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
            <a href="/categories/">
          
        <span class="site-state-item-count">4</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
            <a href="/tags/">
          
        <span class="site-state-item-count">25</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>



      </div>

    </div>
  </aside>
  <div id="sidebar-dimmer"></div>


      </div>
    </main>

    <footer class="footer">
      <div class="footer-inner">
        

<div class="copyright">
  
  &copy; 
  <span itemprop="copyrightYear">2020</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">李喜延</span>
</div>

        








      </div>
    </footer>
  </div>

  
  <script src="/lib/anime.min.js"></script>
  <script src="//cdn.jsdelivr.net/npm/jquery@3/dist/jquery.min.js"></script>
  <script src="//cdn.jsdelivr.net/gh/fancyapps/fancybox@3/dist/jquery.fancybox.min.js"></script>
  <script src="/lib/velocity/velocity.min.js"></script>
  <script src="/lib/velocity/velocity.ui.min.js"></script>

<script src="/js/utils.js"></script>

<script src="/js/motion.js"></script>


<script src="/js/schemes/pisces.js"></script>


<script src="/js/next-boot.js"></script>




  















  

  

</body>
</html>
